#!/usr/bin/python

import random;
import re;

unionfindarr=None;

def initUnionFind(size):
	global unionfindarr;
	unionfindarr=range(size);

def find(x):
	global unionfindarr;
	if( unionfindarr[x]==x):
		return x;
	result=find(unionfindarr[x]);
	unionfindarr[x]=result; #path compression step
	return result;
	

def union(a,b):
	global unionfindarr;
	aroot=find(a);
	broot=find(b);

	if(aroot==broot):
		return False;

	if(random.randint(0,1)):
		unionfindarr[aroot]=broot;
	else:
		unionfindarr[broot]=aroot;
	return True;


#kruskals
def kruskal(edges, numvertices):
	edges=sorted( edges, key=lambda e: e[2]);
	
	initUnionFind(numvertices);
	
	totalweight=0;
	usedweight=0;
	
	for e in edges:
		(a,b,weight)=e;
		totalweight+=weight;
		
		if( union(a,b) ):
			usedweight+=weight;

	return totalweight-usedweight;


def main():
	vertex=0;
	edges=[];

	f=open("network.txt", "r");
	for line in f:
		parsed=re.findall("([\d-]+)", line);
		overtex=0;
		for x in parsed:
			if(x=='-' or overtex<=vertex):
				overtex+=1;
				continue;
			edges.append( (vertex, overtex, int(x)) );
			overtex+=1;	
		vertex+=1;	

	
	print "euler 107: %i" % (kruskal(edges, vertex));

main();	
		

		
